Sudoku Solver

Understand and solve the interview question "Sudoku Solver".

Description#

Write a program to solve Sudoku by filling the empty cells. We will be given a 2D array representing a Sudoku puzzle. For a correct solution each of the digits 1-9 must only occur once in each:

  • Row
  • Column
  • Nine 3x3 sub-boxes of the grid

Let us take a look at an example:

Created with Fabric.js 3.6.6 2 7 5 2 7 3 7 1 5 4 9 8 3 1 8 3 1 5 7 4 9 1 6 2 7 5 1 8 7 8 1 4
Problem

1 of 3

Created with Fabric.js 3.6.6 8 3 1 5 2 7 5 1 8 7 8 1 4 2 7 5 9 8 3 1 7 4 9 1 6 2 7 3 7 1 5 4 As 2 is placed here so, we will not place another 2 in that row, column, or the 3x3 sub matrix.
Rule

2 of 3

Created with Fabric.js 3.6.6 8 2 1 6 7 4 3 5 9 4 9 3 5 8 2 1 6 7 2 3 6 7 1 5 9 4 8 9 5 6 8 3 2 7 1 4 5 8 1 6 9 7 2 4 3 4 7 8 3 6 9 1 2 5 7 3 4 5 9 1 6 2 8 2 7 6 4 1 3 9 8 5 1 5 9 8 4 2 3 6 7 Here’s the solution of the given example
Solution

3 of 3

To solve the puzzle, we will only fill the empty cells. Empty cells are represented by a ‘.’. The array will be passed by reference, so we will not need to return it after solving the puzzle.

Coding exercise#

Sudoku solver

Solution#

While solving Sudoku, we will have to take care of two things. First, we place a number at an empty place. The number must not be present in that row, column, or sub-box. So, we will use constrained programming to keep track of which number we can place in a box and which not. Second, let us assume that we have filled a few empty places but, the choice of numbers was not optimal, and we will have to try some other combination. To do that, we will have to use backtracking.

Let us go over the algorithm:

  1. Start filling the board from board[0][0]
  2. If the value is not ., move on to the next position; otherwise, fill it.
  3. Iterate over each value from 1 to 9:
    1. Check if the value is not already present in that row, column, or 3x3 sub-matrix. If no, then move on to the next value; otherwise, move to the next step.
    2. Place the value on the board and move to the next position recursively.
    3. If we can not place any value from 1 to 9 on a position, then change the value filled in the previous cell and retry.

Let us take a look at an example:

Created with Fabric.js 3.6.6 2 7 5 2 7 3 7 1 5 4 9 8 3 1 8 3 1 5 7 4 9 1 6 2 7 5 1 8 7 8 1 4
Problem

1 of 8

Created with Fabric.js 3.6.6 2 7 3 7 1 5 4 9 8 3 1 8 3 1 5 7 4 9 1 6 2 7 5 1 8 7 8 1 4 1 2 7 5 Start by filling the empty cells with a number from 1 to 9.
board[0][0]

2 of 8

Created with Fabric.js 3.6.6 2 7 3 7 1 5 4 8 3 1 5 7 4 9 1 6 2 7 5 1 8 7 8 1 4 1 is present in the same row, 2 is present in the same cell, 3 is present in the same column. Try placing 4 in this cell. 9 8 3 1 1 2 4 7 5
Conditions check

3 of 8

Created with Fabric.js 3.6.6 9 8 3 1 8 3 1 5 7 4 9 1 6 2 7 5 1 8 7 8 1 4 We can not placeany number hereso we will backtrack to the last position and try another combination 2 3 7 1 5 9 4 5 9 6 2 8 7 1 2 4 7 3 5
Backtracking

4 of 8

Created with Fabric.js 3.6.6 9 8 3 1 8 3 1 5 7 4 9 1 6 2 7 5 1 8 7 8 1 4 We can not placeany number hereas well so let usmove one step back. 1 2 4 7 3 5 2 3 7 1 5 9 4 5 9 6 2 8 7
Backtracking

5 of 8

Created with Fabric.js 3.6.6 9 8 3 1 8 3 1 5 7 4 9 1 6 2 7 5 1 8 7 8 1 4 Let us moveone step back. 1 2 4 7 3 5 5 6 2 8 7 2 3 7 1 5 9 4
Backtracking

6 of 8

Created with Fabric.js 3.6.6 9 8 3 1 8 3 1 5 7 4 9 1 6 2 7 5 1 8 7 8 1 4 1 2 4 7 3 5 5 6 2 8 7 2 3 9 1 5 4 We can place 9 here.
New value

7 of 8

Created with Fabric.js 3.6.6 8 2 1 6 7 4 3 5 9 4 9 3 5 8 2 1 6 7 2 3 6 7 1 5 9 4 8 9 5 6 8 3 2 7 1 4 5 8 1 6 9 7 2 4 3 4 7 8 3 6 9 1 2 5 7 3 4 5 9 1 6 2 8 2 7 6 4 1 3 9 8 5 1 5 9 8 4 2 3 6 7 Follow this process until the board is filled.
Solution

8 of 8

Let us take a look at the solution:

Sudoku Solver

Complexity measures#

Time complexity Space complexity
O(1)O(1) O(1)O(1)

Time complexity#

The time complexity is constant as the board size is fixed. Although it is fixed we must take into account the number of operations taking place. There are 9 possibilities to fill the first cell and 9x8 possibilities to fill the second one. This will make 9!9! operations to fill a row and no more than 9!99!^9 operations to fill the whole board.

Space complexity#

The space complexity is constant because the board size is fixed. It stores 81 elements.

Strong Password Checker

Pacific Atlantic Water Flow